#define _CRT_SECURE_NO_WARNINGS 1

class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        sort(nums.begin(), nums.end());

        int len = nums.size();
        vector<vector<int>> ret(0, vector<int>(3));
        for (int i = 0; i < len - 2;)
        {
            int sum = nums[i];

            for (int j = i + 1; j < len - 1;)
            {
                sum += nums[j];

                int left = j + 1;
                int right = len - 1;
                int mid = 0;
                int fi = 0 - sum;
                while (left <= right)
                {
                    mid = left + (right - left) / 2;
                    if (nums[mid] > fi)
                    {
                        right = mid - 1;
                    }
                    else if (nums[mid] < fi)
                    {
                        left = mid + 1;
                    }
                    else {
                        break;
                    }
                }

                if (nums[mid] == fi)
                {
                    ret.push_back({ nums[i], nums[j], fi });
                }

                int k = 0;
                for (k = j + 1; k < len && nums[j] == nums[k]; ++k);
                j = k;

                sum = nums[i];
            }

            int k = 0;
            for (k = i + 1; k < len && nums[i] == nums[k]; ++k);
            i = k;
        }

        return ret;
    }
};